- Title
- Distance domination and amplifier placement problems
- Creator
- Taylor, S.; Wanless, I. M.; Boland, Natashia
- Relation
- Australasian Journal of Combinatorics Vol. 34, p. 117-136
- Relation
- http://ajc.maths.uq.edu.au/?page=get_volumes&volume=34
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2006
- Description
- We consider the optimization problem defined on a connected undirected graph with given root vertex and a parameter s̅, in which we seek a spanning tree with the smallest number of special (amplifying) vertices such that each vertex in the tree is preceded on its unique path from the root vertex by an amplifying vertex no more than s̅ edges distant. This problem, which we called the amplified spanning tree (AST) problem, is motivated by a practical problem in local access television cable networks. We show that even restricted to planar graphs with no vertex degree exceeding four, AST is NP-complete for every fixed s̅ ≥ 1. Making use of a connection with distance domination problems, we show that two related problems, including total distance domination, are also NP-complete and we derive an approximately upper bound for AST.
- Subject
- amplified spanning tree ( ASP); television; cable networks; vertices
- Identifier
- http://hdl.handle.net/1959.13/939437
- Identifier
- uon:12807
- Identifier
- ISSN:1034-4942
- Language
- eng
- Full Text
- Reviewed
- Hits: 1850
- Visitors: 1955
- Downloads: 136
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | ATTACHMENT01 | Publisher version (open access) | 270 KB | Adobe Acrobat PDF | View Details Download |